//有向无环图的拓扑排序

#include "algraph.h"
#include <iostream>
#include "sqqueue.h"

using namespace std;

//拓扑排序算法 
//对图G 进行拓扑排序，按拓扑有序的顺序输出顶点
template <typename V,typename E,int M>
void TopologicalSort(ALGraph<V,E,M> G)
{
    //计算每个顶点的入度indegree[]
    int indegree[M] = {0};//全部初始化为零
    for (int v = 0; v < G.vexnum; v++)
    {
        for(auto p =G.vexs[v].firstarc; p; p=p->nextarc)
        {
            int w = p->adjvex;
            indegree[w]++;
        }
    }

    //所有入度为零的顶点，入队列Q
    SqQueue<int,M> Q;
    InitQueue(Q);
    for(int v= 0;v<G.vexnum;v++)
    {
        if(indegree[v] == 0){
            EnQueue(Q,v);
        }
    }

    //逐个输出入度为零的顶点并删除之，并将新的入度为零的顶点入队列
    int count = 0;
    while(!QueueEmpty(Q)){
        //取一个入度为零的顶点v
        int v;
        DeQueue(Q,v);
        //输出入度为零的顶点v
        std::cout << G.vexs[v].data;
        count++;
        //顶点v所有邻接点入度减1
        for(auto p = G.vexs[v].firstarc;p;p=p->nextarc){
            int w = p->adjvex;
            indegree[w]--;
            //如果w入度为零则入队列
            if(indegree[w]==0){
                EnQueue(Q,w);
            }
        }
    }
     //结论：如果图中存在回路，提示信息/抛出异常
        if(count < G.vexnum)
           throw "Graph has a cycle";
}
//主函数测试拓扑排序
int main()
{
    ALGraph<char,int> G;
    InitGraph(G);

    auto a = AddVertex(G,'A');
    auto b = AddVertex(G,'B');
    auto c = AddVertex(G,'C');
    auto d = AddVertex(G,'D');
    auto e = AddVertex(G,'E');

    AddArc(G,a,b,1);
    AddArc(G,a,c,1);
    AddArc(G,b,d,1);
    AddArc(G,b,e,1);
    AddArc(G,c,d,1);
    AddArc(G,c,e,1);
    AddArc(G,d,e,1);

    cout << "TopologicalSort:";
    TopologicalSort(G);

    return 0;
}